import java.util.*;

public class Test2 {
    //前k个高频单词:
    //给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。
    //返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。
    public static List<String> topKFrequent(String[] words, int k) {
        //1.每个单词出现次数统计
        Map<String, Integer> map = new HashMap<>();
        for (String s:words) {
            //以前没有
            if (map.get(s) == null){
                map.put(s,1);
            }else {
                //以前有
                int val = map.get(s);
                map.put(s, val + 1);
            }
        }
        //每个单词出现次数统计完毕

        //2.建立小根堆
        PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(k, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if (o1.getValue().compareTo(o2.getValue()) == 0){
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());//小根堆
            }
        });

        //3.现在需要遍历MAP，然后将Map里面的元素建立size为k的小根堆
        for (Map.Entry<String,Integer> entry:map.entrySet()) {
            if (minHeap.size() < k){
                minHeap.offer(entry);

            }else {
                Map.Entry<String,Integer> top = minHeap.peek();
                //1.当前单词出现的频率等于堆顶元素，按照字母顺序，如果当前单词字母的大小小于堆顶元素，则出堆顶元素，入当前元素
                if (top.getValue().compareTo(entry.getValue() )== 0){
                    //频率一样，判断Key,key小的入
                    if (top.getKey().compareTo(entry.getKey()) > 0){
                        //处top,入entry
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }else {
                    //2.当前单词出现的频率大于堆顶元素
                    if (top.getValue().compareTo(entry.getValue()) < 0){
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }
        //4.将小根堆的元素出出来 放到一个集合里面，然后进行逆置
        List<String> list = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            String s = minHeap.poll().getKey();
            list.add(s);
        }
        Collections.reverse(list);
        return list;

    }


    /*统计每个数据出现的次数*/
    public static void func(int[] array){
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i <array.length ; i++) {
            //以前没有
            if (map.get(array[i]) == null){
                map.put(array[i],1);
            }else {
                //以前有
                int val = map.get(array[i]);
                map.put(array[i], val + 1);
            }
        }
        System.out.println(map);
    }
    public static void main(String[] args) {
        int[] array = {1,2,3,2,1};
        func(array);
        String[] s = {"a","b","c","c"};
        List<String> ret = topKFrequent(s , 3);
        System.out.println(ret);
        Map<String,Integer> map = new HashMap();
    }
}
